class Solution {
public:
    int countPrimes(int n) {
        int count = 0;
        vector<bool> signs(n, true); //初始默认所有数为质数
        for (int i = 2; i < n; i++)
        {
            if (signs[i])
            {
                count++;
                for (int j = i + i; j < n; j += i)
                {
                    signs[j] = false; //排除不是质数的数
                }
            }
        }
        return count;
    }
};